#include <stdio.h>
#include <stdlib.h>
#include "seq_list.cpp"

/***
 * 1. 带头结点的单链表 删除重复数据 并将其余数据进行递增排序
 * 2. 大根堆有序 查找大根堆oldvalue值 修改为newvalue
 * */

// 第二题 大根堆
// 以顺序表的形式存储堆
typedef SeqList HeapType;

void InitHeap(HeapType &H)
{
    InitList(H);
}

bool IsEmpty(HeapType H)
{
    return H.length == 0;
}

// 获取结点的父结点
int parent(int k)
{
    return (k - 1) / 2;
}

// 获取结点的左孩子
int leftChild(int k)
{
    return k * 2 + 1;
}

// 获取结点的右孩子
int rightChild(int k)
{
    return k * 2 + 2;
}

// 交换堆中两元素
void swap(HeapType &H, int i, int j)
{
    int temp = H.data[i];
    H.data[i] = H.data[j];
    H.data[j] = temp;
}

// 将指定位置元素上浮至合适位置
void siftUp(HeapType &H, int k)
{
    while (k > 0 && H.data[parent(k)] < H.data[k])
    {
        swap(H, k, parent(k));
        k = parent(k);
    }
}

// 向堆中添加元素
void Add(HeapType &H, int e)
{
    H.data[H.length++] = e;
    siftUp(H, H.length - 1);
}

// 查看堆中的最大元素
int GetMax(HeapType H)
{
    return H.data[0];
}

// 将指定位置的元素下沉至合适位置
void siftDown(HeapType &H, int k)
{
    while (leftChild(k) < H.length)
    {
        int j = leftChild(k);
        if (j + 1 < H.length && H.data[j + 1] > H.data[j])
            j = rightChild(k);

        // data[j] 是左右孩子中的最大值
        if (H.data[k] >= H.data[j])
            break;

        swap(H, k, j);
        k = j;
    }
}

// 取出堆中最大元素
int Pop(HeapType &H)
{
    // 取到堆中最大值
    int e = GetMax(H);
    // 与堆最后一个元素交换位置
    swap(H, 0, H.length - 1);
    // 删除最后一个元素
    H.length--;
    // 第一个元素下沉
    siftDown(H, 0);
    return e;
}

int FindValue(HeapType H, int value, int k)
{
    if (k >= H.length)
        return -1;

    if (H.data[k] == value)
        return k; // 找到元素 返回下标
    if (H.data[k] < value)
        return -1; // 该子数不存在元素value

    int l = FindValue(H, value, leftChild(k));
    if (l != -1)
        return l;

    int r = FindValue(H, value, rightChild(k));
    if (r != -1)
        return r;
    return -1;
}

void Update(HeapType &H, int oldValue, int newValue)
{
    // 查找oldValue位置
    int k = FindValue(H, oldValue, 0);

    // 更新
    if (k != -1) {
        H.data[k] = newValue;
        if (newValue > oldValue)
            siftUp(H, k); // 新元素大需要上浮
        else
            siftDown(H, k); // 新元素小需要下沉
    }
}

int main()
{
    HeapType H;
    InitHeap(H);

    Add(H, 1);
    Add(H, 2);
    Add(H, 5);
    Add(H, 3);
    Add(H, 9);
    PrintList(H);

    int e = Pop(H);
    printf("获得最大元素: %d\n", e);
    PrintList(H);

    Add(H, 8);
    PrintList(H);

    printf("将1更新为10\n");
    Update(H, 1, 10);
    PrintList(H);
    return 0;
}
